package interview;

/**
 * @author: trtan
 * @date: 2021-07-09 16:51
 **/
public class FindMajorityElementLcci {
    /**
     * 若nums中存在一个数字x的数量大于一半
     * 则每次清除两个不同的数字，最后剩余的一定是x
     * 否则说明x的数量不够一半以上
     * @param nums
     * @return int
     * @author trtan
     * @date 2021/7/9 16:56
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        int current = -1;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                current = nums[i];
            } else {
                if (current != nums[i]) {
                    count--;
                } else {
                    count++;
                }
            }
        }
        count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (current == nums[i]) {
                count++;
            }
        }
        return count * 2 > nums.length ? current : -1;
    }
}
